home *** CD-ROM | disk | FTP | other *** search
/ World of Video / World of Video.iso / gfxprograms / 3dprograms / t3dlib / source / sort.c < prev    next >
C/C++ Source or Header  |  1995-02-13  |  1KB  |  49 lines
  1. /* sort.c - Shell-Metzner sort algorithm implemented by Glenn M. Lewis - 7/26/91
  2.  */
  3.  
  4. #include <stdio.h>
  5. #include "t3dlib.h"
  6. #ifdef __STDC__
  7. #include <stdlib.h>
  8. #include <strings.h>
  9. #include "sort_protos.h"
  10. #endif
  11.  
  12. static char rcs_id[] = "$Id: sort.c,v 1.5 1993/01/30 23:43:03 glewis Exp $";
  13.  
  14. void swap_points(desc, p1, p2)
  15. register DESC *desc;
  16. register int p1, p2;
  17. {
  18.     register UWORD *edge;
  19.     register int i;
  20.     XYZ_st tmp;
  21.     if (p1==p2) return;
  22.     for (edge=desc->edge,i=2*desc->ecount; i--; edge++) {
  23.         if (*edge==p1) *edge=p2;
  24.         else if (*edge==p2) *edge=p1;
  25.     }
  26.     bcopy((char*)&desc->pnts[p1], (char*)&tmp, sizeof(XYZ_st));
  27.     bcopy((char*)&desc->pnts[p2], (char*)&desc->pnts[p1], sizeof(XYZ_st));
  28.     bcopy((char*)&tmp, (char*)&desc->pnts[p2], sizeof(XYZ_st));
  29. }
  30.  
  31. void sort_points(desc, cmp)    /* Sort the boxes w/ Shell-Metzner algorithm */
  32. register DESC *desc;
  33. int (*cmp)(P2(XYZ_st*,XYZ_st*));
  34. {
  35.     register int i, j, gap;
  36.  
  37. /* Sort the puppies! */
  38.  
  39.     if (desc->pcount <= 1) return;
  40.     for (gap = desc->pcount/2; gap>0; gap/=2)
  41.         for (i=gap; i<desc->pcount; i++)
  42.             for (j=i-gap; j>=0; j-=gap) {
  43.                 if (cmp(&desc->pnts[j], &desc->pnts[j+gap])<0) break;
  44.                 /* Swap the points */
  45.                 swap_points(desc, j, j+gap);
  46.             }
  47. }
  48.  
  49.